package org.ala.everyday;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。
 *
 * 如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。
 *
 * 返回 优质数对 的总数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
 *
 * 输出：5
 *
 * 解释：
 *
 * 5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。
 *
 * 示例 2：
 *
 * 输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
 *
 * 输出：2
 *
 * 解释：
 *
 * 2个优质数对分别是 (3, 0) 和 (3, 1)。
 *
 *
 *
 * 提示：
 *
 * 1 <= n, m <= 105
 * 1 <= nums1[i], nums2[j] <= 106
 * 1 <= k <= 103
 *
 * @author ala
 * @date 2024-10-10 09:45
 */
public class Q3164 {

    public static void main(String[] args) {
        Q3164 q = new Q3164();

//        int[] nums1 = {1,3,4},
//              nums2 = {1,3,4};
//        int k = 1;

        int[] nums1 = {4, 10},
              nums2 = {1, 7};
        int k = 3;

        System.out.println(q.numberOfPairs(nums1, nums2, k));
    }

    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        return V2(nums1, nums2, k);
    }

    /**
     *  1）n1 能整除 n2 * k，等价于 n1 能整除 k，且 n1 / k 能整除 n2（n2 是 n1 / k 的因子）
     *  2）对每个 n1 / k 分解因子，每个因子记录到hash表计数中
     *  3）枚举每个 nums2，查表累加
     */
    protected long V1(int[] nums1, int[] nums2, int k) {
        Map<Integer, Long> cnts = new HashMap<>();
        for (int n : nums1) {
            if (n % k != 0) {continue;}
            n /= k;

            for (int i = 1 ; i <= Math.sqrt(n) ; i++) {
                if (n % i == 0) {
                    cnts.merge(i, 1l, Long::sum);
                    int i2 = n / i;
                    if (i != i2) {
                        cnts.merge(n / i, 1l, Long::sum);
                    }
                }
            }
        }

        long sum = 0;
        for (int n : nums2) {
            sum += cnts.getOrDefault(n, 0l);
        }
        return sum;
    }
    /**
     *  枚举倍数
     */
    protected long V2(int[] nums1, int[] nums2, int k) {
        //  取 nums1, nums2 每个元素的个数，和各自的最大值
        int[] cnts1 = new int[(int)1e6 + 1], cnts2 = new int[(int)1e6 + 1];
        int mx1 = 0, mx2 = 0;
        for (int n : nums1) {
            mx1 = Math.max(mx1, n);
            cnts1[n]++;
        }
        for (int n : nums2) {
            mx2 = Math.max(mx2, n);
            cnts2[n]++;
        }

        //  遍历nums2，累加每个n2的倍数，累加完后清空（防止本次n2是下个n2的倍数，被累加了两次）
        long res = 0;
        for (int n : nums2) {
            if (cnts2[n] != 0) {
                for (int d = n * k, i = d ; i <= mx1 ; i += d) {
                    res += (long)cnts1[i] * (long)cnts2[n];
                }
                cnts2[n] = 0;
            }
        }
        return res;
    }
}
